
#ifndef GRAPH_GRAPH_H
#define GRAPH_GRAPH_H

//      图的一些重要概念
// ----------------------------------------------------------------------------------------------------------
// 完全图（最稠密的图）：跟完全二叉树类似，在有n个顶点的无向图中，有n*(n-1)/2条边
// 即任意两个顶点之间有且仅有一条边，则称此图为无向完全图
// 若为有向图，则有n*(n-1)条边
// 即任意两个顶点之间有且仅有方向相反的边

// 邻接顶点：在无向图中G中，若(u, v)是E(G)中的一条边
// 则称u和v互为邻接顶点，并称边(u,v)依附于顶点u和v
// 在有向图G中，若<u, v>是E(G)中的一条边
// 则称顶点u邻接到v，顶点v邻接自顶点u，并称边<u, v>与顶点u和顶点v相关联。

// 顶点的度：顶点v的度是指与它相关联的边的条数，记作deg(v)。
// 在有向图中，顶点的度等于该顶点的入度与出度之和，其中顶点v的入度是以v为终点的有向边的条数，记作indev(v)
// 顶点v的出度是以v为起始点的有向边的条数，记作outdev(v)。
// 因此：dev(v) = indev(v) + outdev(v)。
// 注意：对于无向图，顶点的度等于该顶点的入度和出度，即dev(v) = indev(v) = outdev(v)。

// 路径：在图G = (V， E)中，若从顶点vi出发有一组边使其可到达顶点vj
// 则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj的路径

// 路径长度：对于不带权的图，一条路径的路径长度是指该路径上的边的条数；
// 对于带权的图，一条路径的路径长度是指该路径上各个边权值的总和

// 连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的
// 如果图中任意一对顶点都是连通的，则称此图为连通图

// 强连通图：在有向图中，若在每一对顶点vi和vj之间都存在一条vi到vj的路径，也存在一条从vj到vi的路径
// 则称此图为强连通图

// 生成树（无向图的概念）：一个连通图的最小连通子图称作该图的生成树，有n个顶点的连通图的生成树有n个顶点和n-1条边

// 最小生成树：对应生成树的概念，考虑权值，n-1条边的权值加起来最小的生成树叫做最小生成树
// ----------------------------------------------------------------------------------------------------------

#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <functional>

// 顶点Vertex 权值Weight
namespace matrix
{
    template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
    class Graph
    {
        typedef Graph<V, W, MAX_W, Direction> Self;
    public:
        Graph() = default;
        // 图的创建
        // 1.IO输入 -- 不方便测试
        // 2.图结构关系写到文件，读取文件
        // 3.手动添加边
        Graph(const V* a, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0 ; i < n ; i++){
                _vertexs.push_back(a[i]);
                _indexMap[a[i]] = i;
            }

            _matrix.resize(n);
            for (size_t i = 0 ; i < _matrix.size() ; i++){
                _matrix[i].resize(n, MAX_W);
            }
        }

        // 查找顶点的下标
        size_t GetVertexIndex(const V& v)
        {
            // 检查一下，预防v为错误输入
            auto it = _indexMap.find(v);
            if (it != _indexMap.end()){
                return it->second;
            }
            else return -1;
        }

        void _AddEdge(size_t srci, size_t dsti, const W& w)
        {
            _matrix[srci][dsti] = w;
            // 如果是无向
            if (!Direction){
                _matrix[dsti][srci] = w;
            }
        }

        void AddEdge(const V& src, const V& dst, const W& w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);

            _AddEdge(srci, dsti, w);
        }

        void Print()
        {
            // 打印顶点
            for (size_t i = 0 ; i < _vertexs.size() ; i++){
                cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
            }
            cout << endl;

            // 矩阵打印
            // 横下标
            cout << "  ";
            for (size_t i = 0 ; i < _vertexs.size() ; i++){
                cout << i << " ";
            }
            cout << endl;

            for (size_t i = 0 ; i < _matrix.size() ; i++){
                cout << i << " "; // 竖下标
                for (size_t j = 0 ; j < _matrix[i].size() ; j++){
//                    cout << _matrix[i][j] << " ";
                    if (_matrix[i][j] == MAX_W) cout << "* ";
                    else cout << _matrix[i][j] << " ";
                }
                cout << endl;
            }
            cout << endl;

            for (size_t i = 0; i < _matrix.size(); ++i)
            {
                for (size_t j = 0; j < _matrix[i].size(); ++j)
                {
                    if (i < j && _matrix[i][j] != MAX_W)
                    {
                        cout << _vertexs[i] << "->" << _vertexs[j] << ":" << _matrix[i][j] << endl;
                    }
                }
            }
        }

//        void BFS(const V& src)
//        {
//            size_t srci = GetVertexIndex(src);
//
//            // 队列和标记数组
//            queue<int> q;
//            vector<bool> visited(_vertexs.size(), false);
//
//            q.push(srci);
//            visited[srci] = true;
//
//            size_t n = _vertexs.size();
//            while (!q.empty()){
//                int front = q.front();
//                q.pop();
//                cout << front << ":" << _vertexs[front] << endl;
//
//                // 把front顶点的邻接顶点入队列
//                for (size_t i = 0 ; i < n ; i++){
//                    if (_matrix[front][i] != MAX_W){
//                        if (!visited[i]) {
//                            // 防止重复入队
//                            q.push(i);
//                            visited[i] = true;
//                        }
//                    }
//                }
//            }
//            cout << endl;
//        }

        // 图的层序和深度遍历
        // 给的图如果不是连通图，以某个点位起点就没有遍历完成
        // 此时怎么保证遍历完剩下的顶点？
        // 在visited数组中赵没有访问过的顶点继续访问
        void BFS(const V& src)
        {
            size_t srci = GetVertexIndex(src);

            // 队列和标记数组
            queue<int> q;
            vector<bool> visited(_vertexs.size(), false);

            q.push(srci);
            visited[srci] = true;
            int levelSize = 1;

            size_t n = _vertexs.size();
            while (!q.empty()){
                // 一层打印一行
                for (int i = 0 ; i < levelSize ; i++){
                    int front = q.front();
                    q.pop();
                    cout << front << ":" << _vertexs[front] << " ";

                    // 把front顶点的邻接顶点入队列
                    for (size_t i = 0 ; i < n ; i++){
                        if (_matrix[front][i] != MAX_W){
                            if (!visited[i]) {
                                // 防止重复入队
                                q.push(i);
                                visited[i] = true;
                            }
                        }
                    }
                }
                cout << endl;
                levelSize = q.size();
            }
            cout << endl;
        }

        void _DFS(size_t srci, vector<bool>& visited){
            cout << srci << ":" << _vertexs[srci] << endl;
            visited[srci] = true;

            // 找一个srci相邻的未访问点，去往深度遍历
            for (size_t i = 0 ; i < _vertexs.size() ; i++){
                if (_matrix[srci][i] != MAX_W && !visited[i]){
                    _DFS(i, visited);
                }
            }
        }

        void DFS(const V& src)
        {
            size_t srci = GetVertexIndex(src);
            vector<bool> visited(_vertexs.size(), false);

            _DFS(srci, visited);
        }

        struct Edge
        {
            size_t _srci;
            size_t _dsti;
            W _w;

            Edge(size_t srci, size_t dsti, const W& w)
            :_srci(srci)
            ,_dsti(dsti)
            ,_w(w)
            {}

            bool operator>(const Edge& e) const
            {
                return _w > e._w;
            }
        };

        // 最小生成树不一定唯一
        // 判环可以采用并查集
        W Kruskal(Self& minTree){
            size_t n = _vertexs.size();

            minTree._vertexs = _vertexs;
            minTree._indexMap = _indexMap;
            minTree._matrix.resize(n);
            for (size_t i = 0 ; i < n ; i++){
                minTree._matrix[i].resize(n, MAX_W);
            }

            priority_queue<Edge, vector<Edge>, greater<Edge>> minque;
            for (size_t i = 0 ; i < n ; i++){
                for (size_t j = 0 ; j < n ; j++){
                    if (i < j && _matrix[i][j] != MAX_W){ // 无向图避免重复添加
                        minque.push(Edge(i, j, _matrix[i][j]));
                    }
                }
            }

            // 选出n-1条边
            int size = 0;
            W totalW = W();
            UnionFindSet ufs(n);
            while (!minque.empty()){
                Edge min = minque.top();
                minque.pop();

                // 选出一条边后看在不在同一个集合
                if (!ufs.isInset(min._srci, min._dsti)){
                    // 打印选出的边
                    cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti]
                         << ":" << min._w << endl;

                    minTree._AddEdge(min._srci, min._dsti, min._w);
                    ufs.Union(min._srci, min._dsti);
                    size++;
                    totalW += min._w;
                }
            }

            // 若连通
            if (size == n - 1){
                return totalW;
            }
            // 若不连通
            else return W();
        }

        // Prim思路天然避环
        W Prim(Self& minTree, const V& src) {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();

            minTree._vertexs = _vertexs;
            minTree._indexMap = _indexMap;
            minTree._matrix.resize(n);
            for (size_t i = 0; i < n; i++) {
                minTree._matrix[i].resize(n, MAX_W);
            }

//            set<int> X;
//            set<int> Y;
//            X.insert(srci);
//            for (size_t i = 0 ; i < n ; i++){
//                if (i != srci) Y.insert(i);
//            }

            vector<bool> X(n, false);
            vector<bool> Y(n, true);
            X[srci] = true;
            Y[srci] = false;

            // 从X->Y集合中连接的边里面选出最小的边
            // 怎么判断最小边?
            priority_queue<Edge, vector<Edge>, greater<Edge>> minq;
            // 先把srci连接的边添加到队列中
            for (size_t i = 0 ; i < n ; i++){
                if (_matrix[srci][i] != MAX_W){
                    minq.push(Edge(srci, i, _matrix[srci][i]));
                }
            }

            size_t size = 0;
            W totalW = W();
            while (!minq.empty()){
                Edge min = minq.top();
                minq.pop();

                // 如果最小边的目标点也在X集合，则成环
                if (X[min._dsti]){ // 不必考虑起始点
                    cout << "构成环：";
                    cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":"
                         << min._w << endl;
                }
                else {
                    minTree._AddEdge(min._srci, min._dsti, min._w);
                    cout << _vertexs[min._srci] << "->" << _vertexs[min._dsti] << ":"
                         << min._w << endl;

                    X[min._dsti] = true;
                    Y[min._srci] = false;
                    size++;
                    totalW += min._w;
                    if (size == n - 1) break;

                    for (size_t i = 0 ; i < n ; i++){
                        if (_matrix[min._dsti][i] != MAX_W && !X[i]){
                            minq.push(Edge(min._dsti, i, _matrix[min._dsti][i]));
                        }
                    }
                }
            }

            // 若连通
            if (size == n - 1){
                return totalW;
            }
            // 若不连通
            else return W();
        }

        void PrintShortPath(const V& src, const vector<W>& dist,const vector<int>& pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();

            for (size_t i = 0 ; i < n ; i++){
                if (i != srci){
                    // 找出i顶点的路径
                    vector<int> path;
                    size_t parenti = i;
                    while (parenti != srci){
                        path.push_back(parenti);
                        parenti = pPath[parenti];
                    }
                    path.push_back(srci);
                    reverse(path.begin(), path.end());

                    for (auto index : path){
                        cout << _vertexs[index] << "->";
                    }
                    cout << dist[i] << endl;
                }
            }
        }

        // 最短路径问题：从在带权有向图G中的某一顶点出发，找出一条通往另一顶点的最短路径，最短也就是
        //        沿路径各边的权值总和达到最小。
        // 请注意，Dijkstra算法存在的问题是不支持图中带负权路径，如果带有负权路径，则可能会找不到一些路
        // 径的最短路径。

        // 用一个数组dist，其中dist[i]表示s->{syztx}的最短路径
        // pPath存储路径前一个顶点下标
        // 时间复杂度O(N^2) 空间复杂度O(N)
        void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
        {
            size_t srci = GetVertexIndex(src);
            size_t n = _vertexs.size();
            dist.resize(n, MAX_W);
            pPath.resize(n, -1);

            dist[srci] = 0;
            pPath[srci] = srci;

            // 已经确定是最短路径的顶点集合
            vector<bool> S(n, false);
            for (size_t j = 0 ; j < n ; j++)
            {
                // 选最短路径的顶点且不在S，并更新其他路径
                int u = 0;
                W min = MAX_W;
                for (size_t i = 0 ; i < n ; i++){
                    if (!S[i] && dist[i] < min){
                        u = i;
                        min = dist[i];
                    }
                }

                // u是不在S中的点
                S[u] = true;

                // 松弛更新u连接的顶点v srci -> u + u -> v < srci -> v
                for (size_t v = 0 ; v < n ; v++){
                    if (!S[v] && _matrix[u][v] != MAX_W && dist[u] + _matrix[u][v] < dist[v]){
                        dist[v] = dist[u] + _matrix[u][v];
                        pPath[v] = u;
                    }
                }
            }
        }

        // 时间复杂度O(N^3) 时间复杂度O(N)
        bool BellmanFord(const V& src, vector<W>& dist, vector<int>& parentPath)
        {
            size_t n = _vertexs.size();
            size_t srci = GetVertexIndex(src);

            // vector<W> dist,记录srci-其他顶点最短路径权值数组
            dist.resize(n, MAX_W);

            // vector<int> parentPath 记录srci-其他顶点最短路径父顶点数组
            parentPath.resize(n, -1);

            // 先更新srci->srci为缺省值
            dist[srci] = W();

            // i->j 更新一次
            // 总体最多更新n轮
            for (size_t k = 0 ; k < n ; k++) {
                // i -> j 更新松弛
                bool update = false;
                for (size_t i = 0; i < n; i++) {
                    for (size_t j = 0; j < n; j++) {
                        // srci -> i + i -> j
                        if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
                            update = true;
                            dist[j] = dist[i] + _matrix[i][j];
                            parentPath[j] = i;
                        }
                    }
                }
                // 如果这个轮次中没有更新出最短路径，那么后续轮次就不需要再走了
                if (!update) break;
            }

            // 还能更新就是带负权回路
            for (size_t i = 0; i < n; i++) {
                for (size_t j = 0; j < n; j++) {
                    // srci -> i + i -> j
                    if (_matrix[i][j] != MAX_W && dist[i] + _matrix[i][j] < dist[j]) {
                        return false;
                    }
                }
            }

            return true;
        }

        void FloydWarShall(vector<vector<W>>& vvDist, vector<vector<int>>&vvpPath)
        {
            size_t n = _vertexs.size();
            vvDist.resize(n);
            vvpPath.resize(n);

            // 初始化权值和路径矩阵
            for (size_t i = 0 ; i < n ; ++i)
            {
                vvDist[i].resize(n, MAX_W);
                vvpPath[i].resize(n, -1);
            }

            // 直接相连的边更新一下
            for (size_t i = 0 ; i < n ; i++){
                for (size_t j = 0 ; j < n ; j++){
                    if (_matrix[i][j] != MAX_W){
                        vvDist[i][j] = _matrix[i][j];
                        vvpPath[i][j] = i;
                    }

                    if (i == j){
                        vvDist[i][j] = 0;
                    }
                }
            }

            // 最短路径的更新i -> {其他顶点} -> j
            // k 作为中间点，尝试去更新i->j的路径
            for(size_t k = 0 ; k < n ; k++){
                for (size_t i = 0 ; i < n ; i++){
                    for (size_t j = 0 ; j < n ; j++){
                        if (vvDist[i][k] != MAX_W && vvDist[k][j] != MAX_W
                            && vvDist[i][k] + vvDist[k][j] < vvDist[i][j])
                        {
                            vvDist[i][j] = vvDist[i][k] + vvDist[k][j];
                            // 找跟j相连的上一个邻接顶点
                            // 如果k->j 直接相连，上一个点就k，vvpPath[k][j]存就是k
                            // 如果k->j 没有直接相连，k->...->x->j，vvpPath[k][j]存就是x
                            vvpPath[i][j] = vvpPath[k][j];
                        }
                    }
                }
            }

        }

    private:
        vector<V> _vertexs; // 顶点集合
        map<V, int> _indexMap; // 顶点映射的下标
        vector<vector<W>> _matrix; // 邻接矩阵
    };
}

namespace link_table
{
    template<class W>
    struct Edge
    {
        // 看需求是否需要起始点的下标
        // 这里存的是出边表
        // int srci;
        int _dsti; // 目标点的下标
        W _w; // 权值
        Edge<W>* _next;

        Edge(int dsti, const W& w)
            :_dsti(dsti)
            ,_w(w)
            ,_next(nullptr)
        {}
    };
    template<class V, class W, bool Direction = false>
    class Graph
    {
        typedef Edge<W> Edge;
    public:
        // 图的创建
        // 1.IO输入 -- 不方便测试
        // 2.图结构关系写到文件，读取文件
        // 3.手动添加边
        Graph(const V* a, size_t n)
        {
            _vertexs.reserve(n);
            for (size_t i = 0 ; i < n ; i++){
                _vertexs.push_back(a[i]);
                _indexMap[a[i]] = i;
            }

            _tables.resize(n, nullptr);
        }

        // 查找顶点的下标
        size_t GetVertexIndex(const V& v)
        {
            // 检查一下，预防v为错误输入
            auto it = _indexMap.find(v);
            if (it != _indexMap.end()){
                return it->second;
            }
            else return -1;
        }

        void AddEdge(const V& src, const V& dst, const W& w)
        {
            size_t srci = GetVertexIndex(src);
            size_t dsti = GetVertexIndex(dst);

            // 1->2（头插）
            Edge* eg = new Edge(dsti, w);
            eg->_next = _tables[srci];
            _tables[srci] = eg;

            // 如果是无向，还要2->1（头插）
            if (!Direction){
                Edge* eg = new Edge(srci, w);
                eg->_next = _tables[dsti];
                _tables[dsti] = eg;
            }
        }

        void Print()
        {
            // 打印顶点
            for (size_t i = 0 ; i < _vertexs.size() ; i++){
                cout << "[" << i << "]" << "->" << _vertexs[i] << endl;
            }
            cout << endl;

            for (size_t i = 0 ; i < _tables.size() ; i++){
                cout << _vertexs[i] << "[" << i << "]->";
                Edge* cur = _tables[i];

                while(cur){
                    cout << _vertexs[cur->_dsti] << "[" << cur->_dsti << "]" << cur->_w << "->";
                    cur = cur->_next;
                }
                cout << "nullptr"<< endl;
            }
        }


    private:
        vector<V> _vertexs; // 顶点集合
        map<V, int> _indexMap; // 顶点映射的下标
        vector<Edge*> _tables; // 邻接表
    };
}


// 邻接矩阵和邻接表其实属于相辅相成，各有优缺点的互补结构

//   邻接矩阵：
// 邻接矩阵存储方式非常适合稠密图
// 邻接矩阵O(1)判断两个顶点的连接关系，并取到权值
// 相对而言不适合查找一个顶点连接所有边 --O(N)

//   邻接表：
// 适合存储稀疏图
// 适合查找一个顶点连接出去的边
// 不适合确定两个顶点是否相连及权值

#endif //GRAPH_GRAPH_H
